package algorithm.search;

/**
 * 二分查找
 * @author bingo
 * @create 2018-02-26 18:01
 **/
public class BinarySearch {

    public int binarySearch(Integer[] arr,int n,int target){
        int l=0,r=n-1;
        while (l<=r){
            int mid = (l+r)/2;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]>target){
                r=mid-1;
            }else if(arr[mid]<target){
                l=mid+1;
            }else{
                return  -1;
            }
            }
        return -1;
    }
    public int binarySearch2(Integer[] arr,int n,int target){
        int l=0,r=n-1;
        int index = find(arr,l,r,target);
        return  index;
     }

    public int find(Integer[] arr,int l,int r, int target){
        if(l > r){
            return -1;
        }
        int mid = (l+r)/2;
        if(arr[mid]==target){
            return  mid;
        }
        if(arr[mid]>target){
            r=mid-1;
        }
        if(arr[mid]<target){
            l=mid+1;
        }
        int index =   find(arr,l,r,target);
        return index;
    }


    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1,1,2,3,4,5,6,7,8,9};
        BinarySearch binarySearch = new BinarySearch();
        int index  = binarySearch.binarySearch(arr,arr.length,9);
        int index2 = binarySearch.binarySearch2(arr,arr.length,9);
        System.out.println("index="+index);
        System.out.println("index2="+index2);
    }

}
